The present invention relates to increasing the execution speed of object-oriented programs. More specifically, the invention relates to utilizing information collected during execution of an object-oriented program for subsequent executions.
The fundamental idea behind object-oriented languages is the combination of both data and the methods (or functions) that operate on that data into a single unit, which is called an object. An object's functions typically provide the only way to access the data that is encapsulated by the object. The data is accessed by sending a message to the object instructing the object to invoke the method specified by the message.
Efficient message dispatch is of paramount importance in object-oriented languages. This is because message dispatch is a very frequent operation in object-oriented programs and is performed at runtime; therefore, it should be as fast as possible. Message dispatch, however, is far from being a trivial operation. Unlike procedural programming languages (e.g., the C programming language) that can determine a function's address before runtime, object-oriented languages must determine the method that handles a message that has been dispatched to a receiver object at runtime, and it may involve an extensive search.
In order to better understand the complexities of message dispatch, FIG. 1 shows a class hierarchy including methods of each class. A class hierarchy 1 includes at its root a parent class A 3 that defines two virtual functions foo( ) and bar( ). Virtual functions are functions that may be defined in a parent class and redefined in the children classes. Class B 5 and class C 7 inherit the data and methods of the parent class A. As shown, class B does not redefine either of the virtual functions foo and bar. However, class C redefines the virtual function foo. When an object of class C is requested to invoke the method foo, the method invoked will be the method defined by the class C, not the parent class A. Classes D 9 and E 11 also redefine the method foo.
As it is generally impossible to determine the class of an object statically, the search for the correct method is performed at runtime, during message dispatch. There are many known techniques for implementing method dispatch. For example, FIG. 2 shows an inline cache. Assume a method 51 was originally as follows:
main( )
{
. . .
x.foo( );
. . .
}
Thus, the method main includes a statement x.foo( ) in order to invoke the method foo of object x.
During runtime, the system would have to determine to which class object x belongs before the method to handle the method could be invoked. With an inline cache, the first time the system determines the class to which object x belongs, a direct call to the class's method is written into the computer code.
Assuming that object x is a member of class A, the call x.foo( ) is changed to a direct call A::foo( ). The arrow specifies a method foo for class A 53. Since the object x may not be of class A every time, a prolog 55 verifies that the object x is of the correct class, which is represented as the expression x=A meaning that it is determined if the class of object x is equal to class A. The class of an object may be determined from a value stored in the object. If the object is of the correct class, a jump is performed to method code 57 that handles the message.
Returning to prolog 55, if the object is not of class A, a method lookup routine is called in order to determine the correct method. Once the correct method is found, the system updates the message dispatch (or call) site with a direct call to that method. Additionally, the system updates the prolog to specify the new class. As an example, assume that the first time that the system encountered x.foo ( ), object x was of class A and the data structures were modified as shown in FIG. 2.
Once the data structures are modified as shown, subsequent calls to x.foo( ) will be substantially more efficient if object x is of class A. However, if object x subsequently is of class B, prolog 55 calls a method lookup routine to find the method and let's assume it determines that object x is now of class B. Referring again to FIG. 1, it is seen that the method foo for class B is the same method foo as defined in class A (ie., class B did not redefine the virtual function foo). Accordingly, the message dispatch in method 51 will be changed to B::foo ( ) and the condition in prolog 55 will be changed to x=B.
An inline cache may be an efficient way of implementing message dispatch if the object at a call site bar remains the same class. However, if the object is of multiple classes, the system is continually calling the method lookup routine and patching the call site and prolog. Thus, the system may be actually less efficient.
Another technique for implementing message dispatch is the use of a polymorphic inline cache as shown in FIG. 3. As before, a method 101 originally included a method dispatch x.foo( ). With a polymorphic inline cache, a stub 103 is generated such that it is able to perform the message dispatch for different receiver types. The original message dispatch is overwritten with a call to the polymorphic inline cache stub 103. Each time a new receiver type is encountered, a statement is added to the stub. As shown, three different receiver types have been encountered thus far. If the receiver type has been encountered, a call is made to the method to handle the message for that receiver type. Otherwise, the method lookup routine is called to determine the appropriate method to handle the message. Typically, a new statement will be added to stub 103 in order to handle each new receiver type.
The polymorphic inline cache is more flexible than the inline cache as it is able to handle multiple receiver types. However, a drawback of the polymorphic inline cache is that as more receiver types are encountered, the stub continues to grow and it becomes less and less efficient at performing message dispatch. For example, the system may need to plow through multiple if statements before finding the right method to handle the message.
FIG. 4 shows another message dispatch technique called hashing. In hashing, the original message dispatch in a method 151, x.foo( ), is overwritten with a call to a hash function 153. The hash function hashes the receiver type and the message in order to form a hash key, which is typically an index into a hash table 155. The hash table includes an index 157, receiver types 159, messages 161, and methods 163. Once the hash function hashes to a row in hash table 155, the receiver type and message are retrieved from columns 159 and 161 of the hash table. If the receiver type and message at the call site match the receiver type and message in the row of the hash table, the method specified in column 163 of hash table 155 is invoked. Otherwise, a method lookup routine is called in order to find the correct method. Typically, the new method is then added to the hash table.
Although hashing is the most flexible message dispatch technique we have described thus far, it is more computationally and storage intensive than the other techniques. Another drawback of the message dispatch techniques we have described is that none of the techniques are site specific. In other words, none of the message dispatch techniques provide the flexibility of handling message dispatches at different call sites in a different manner. Other method dispatch techniques are described in “Message Dispatch on Pipelined Processors,” by K. Driesen et al., ECOOP, 1995, which is hereby incorporated by reference for all purposes.
None of the message dispatch techniques described above allow for the receiver type information that is collected to be utilized during a subsequent execution of the program. Additionally, it would be desirable if inlining information was available during subsequent program executions. Accordingly, there is a need for techniques that allow for collected receiver type and/or inlining information to be utilized in later runs of the program.